#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: find_node.py 
@version:
@time: 2024/01/17

解读题目，查找一棵二叉搜索树中所有值介于Left和Right之间的节点。
解决该问题最直接的想法就是遍历这棵二叉树的每个节点，
将每个节点的值与Left和Right对比，将符合要求的节点累加，
这样的时间复杂度与节点数相关，空间复杂度与树的高度相关。

但如此依赖，并没有利用二叉搜索树的特点。由于二叉搜索树及其所有子树具有左子树小于根节点、右子树大于根节点的特点，
因此可以利用这一特点在遍历中免去一部分的遍历。

当根节点值小于Left时，其左子树的所有节点均小于Left，不可能满足要求；当根节点值大于Right时，其右子树的所有节点均大于Right，
也不可能满足要求。这两类数无须遍历，可以降低复杂度。

深度优先搜索算法的基本思想，”一查到底，无果则回溯“
"""


class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Btree:
    def __init__(self, node=None):
        self.root = node


value = [12, 5, 18, 2, 9, 15, 19, 17]
node = []
for i in value:
    node.append(Node(i))
b = Btree(node[0])

b.root.left = node[1]
b.root.right = node[2]

b.root.left.left = node[3]
b.root.left.right = node[4]

b.root.right.left = node[5]
b.root.right.right = node[6]

b.root.right.left.right = node[7]


class Solution:
    num = 0

    def findNode(self, Root, Left, Right):

        def dfs(root):
            if root:
                if root.val < Left:
                    dfs(root.right)
                elif root.val > Right:
                    dfs(root.left)
                else:
                    self.num += root.val
                    dfs(root.right)
                    dfs(root.left)

        self.num = 0
        dfs(Root)
        return self.num


print(Solution().findNode(b.root, 2, 19))
